package application;

import zhengqc.common.Tuple;
import zhengqc.map.AVLTreeMap;
import zhengqc.map.Map;
import zhengqc.queue.LoopQueue;
import zhengqc.queue.Queue;

import java.io.File;
import java.io.IOException;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

public class MazeProblem {
    private char ACCESS = '.';
    private char BLOCK = '#';
    private char[][] maze;
    private int row;
    private int col;
    private boolean valid;
    private int[][] dirs;
    private Tuple<Integer, Integer> target;
    public MazeProblem() {
        // 四连通
        this.dirs = new int[][]{ {-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        this.valid = false;
    }
    public void setMaze(String filename) {
        File file = new File(filename);
        try (Scanner scanner = new Scanner(file)) {
            this.row = scanner.nextInt();
            this.col = scanner.nextInt();
            this.maze = new char[this.row][this.col];
            for (int i = 0; i < this.row; ++i) {
                this.maze[i] = scanner.next().toCharArray();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (this.maze[0][0] != BLOCK && this.maze[this.row-1][this.col-1] != BLOCK) {
            this.valid = true;
            this.target = new Tuple<>(this.row-1, this.col-1);
        }
    }
    public void printMaze() {
        StringBuilder sb = new StringBuilder(String.format("maze - row: %d, col: %d", this.row, this.col)).append("\n");
        for (int i = 0; i < this.row; ++i) {
            for (int j = 0; j < this.col; ++j) {
                sb.append(this.maze[i][j]).append(' ');
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
    private boolean inArea(int r, int c) {
        if (r < 0 || r >= this.row || c < 0 || c >= this.col) {
            return false;
        }
        return true;
    }
    // 使用 BFS
    public LinkedList<Tuple<Integer, Integer>> getShortestPath() {
        if (!this.valid) return null;
        boolean flag = false;

        Queue<Tuple<Integer, Integer>> queue = new LoopQueue<>();
        Map<Tuple<Integer, Integer>, Tuple<Integer, Integer>> precedes = new AVLTreeMap<>();
        Tuple<Integer, Integer> start = new Tuple<>(0, 0);
        queue.enqueue(start);
        precedes.put(start, start);
        while ( !queue.isEmpty() ) {
            Tuple<Integer, Integer> current = queue.dequeue();
            if ( current.equals(this.target) ) {
                flag = true;
                break;
            }
            for (int[] d: this.dirs) {
                int dx = d[0], dy = d[1];
                int nx = current.first + dx, ny = current.second + dy;
                if ( !inArea(nx, ny) || this.maze[nx][ny] == BLOCK) continue;
                Tuple<Integer, Integer> np = new Tuple<>(nx, ny);
                if ( !precedes.containsKey(np) ) {
                    queue.enqueue(np);
                    precedes.put(np, current);
                }
            }
        }
        LinkedList<Tuple<Integer, Integer>> path = new LinkedList<>();
        if (!flag) {
            return path;
        }
        Tuple<Integer, Integer> current = this.target;
        while (current != start) {
            path.add(current);
            current = precedes.get(current);
        }
        path.add(start);
        Collections.reverse(path);
        return path;
    }
}
